package leetcode.editor.cn;//给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
//
// 算法的时间复杂度应该为 O(log (m+n)) 。
//
//
//
// 示例 1：
//
//
//输入：nums1 = [1,3], nums2 = [2]
//输出：2.00000
//解释：合并数组 = [1,2,3] ，中位数 2
//
//
// 示例 2：
//
//
//输入：nums1 = [1,2], nums2 = [3,4]
//输出：2.50000
//解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5
//
//
// 示例 3：
//
//
//输入：nums1 = [0,0], nums2 = [0,0]
//输出：0.00000
//
//
// 示例 4：
//
//
//输入：nums1 = [], nums2 = [1]
//输出：1.00000
//
//
// 示例 5：
//
//
//输入：nums1 = [2], nums2 = []
//输出：2.00000
//
//
//
//
// 提示：
//
//
// nums1.length == m
// nums2.length == n
// 0 <= m <= 1000
// 0 <= n <= 1000
// 1 <= m + n <= 2000
// -106 <= nums1[i], nums2[i] <= 106
//
// Related Topics 数组 二分查找 分治
// 👍 4757 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
 class Solution4 {
    //分治法
    //https://blog.csdn.net/nipirennipi136/article/details/108004315
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int len1=nums1.length,len2=nums2.length;
        //对长度短的数组进行划分，保证另一数组边界不溢出
        if(len1>len2) return findMedianSortedArrays(nums2,nums1);
        //找到两个数组的分割线，使得分割线左边元素<右边元素
        //即nums1[i-1]<nums2[j]&&nums2[j-1]<nums1[i]
        int totalLeft=len1+(len2-len1+1)/2;//分割线左边的元素总个数=总长度n/2
        //i、j分别为两数组分割线右边元素下标，j可由i求出
        int i,j,left=0,right=len1;
        while(left<right){
            i=left+(right-left+1)/2;
            j=totalLeft-i;
            if(nums1[i-1]>nums2[j]) right=i-1;
            else left=i;
        }
        i=left;
        j=totalLeft-i;
        int l1,r1,l2,r2;//lr分别为分割线左右元素
        l1=i>0?nums1[i-1]:Integer.MIN_VALUE;
        r1=i!=len1?nums1[i]:Integer.MAX_VALUE;
        l2=j>0?nums2[j-1]:Integer.MIN_VALUE;
        r2=j!=len2 ? nums2[j]:Integer.MAX_VALUE;
        if((len1+len2)%2==1) return Math.max(l1,l2);
        return ((double)(Math.max(l1,l2)+Math.min(r1,r2)))/2;
    }
    public double findMedianSortedArrays01(int[] nums1, int[] nums2) {
        int len1 = nums1.length, len2 = nums2.length, n = len1 + len2, key = n / 2;
        int res = Math.min(len1 != 0 ? nums1[0] : 106, len2 != 0 ? nums2[0] : 106), pre = res;
        int i, j;
        //找到第k个元素,i+j即为本次循环要找的第i+j个元素
        for (i = 0, j = 0; i+j<=key; ) {
            pre = res;
            if(i>=len1) res=nums2[j++];
            else if(j>=len2) res=nums1[i++];
            else{
                if (nums1[i] < nums2[j]) res = nums1[i++];
                else res = nums2[j++];
            }
        }
        if ((len1 + len2) % 2 == 1) return res;
        return ((double) pre + (double) res) / 2;
    }
}
//leetcode submit region end(Prohibit modification and deletion)
